package chapter02;

/**
 * 不用递归，写出快速求幂的程序。
 */
public class Q23 {

    public static void main(String[] args) {

        double pow = pow(2, 10);
        System.out.println(pow);

        double pow2 = pow2(2, -4);
        System.out.println(pow2);
    }

    /**
     * 递归的方法(正&负数次幂)
     * @param x
     * @param N
     * @return
     */
    public static double pow(double x, long N) {
        if (N >= 0) {
            return quickMul(x, N);
        }else {
            return 1 / quickMul(x, -N);
        }
    }

    /**
     * 递归的方法(正数次幂)
     * @param x
     * @param N
     * @return
     */
    public static double quickMul(double x, long N) {
        if (N == 0) {
            return 1.0;
        }
        double pow = quickMul(x, N / 2);
        if (N % 2 == 0) {
            return pow * pow;
        }else {
            return pow * pow * x;
        }
    }

    /**
     * 递归的方法(正&负数次幂)
     * @param x
     * @param N
     * @return
     */
    public static double pow2(double x, long N) {
        if (N >= 0) {
            return quickMul(x, N);
        }else {
            return 1 / quickMul(x, -N);
        }
    }

    public static double quickMul2(double x, long N) {
        double ans = 1.0;
        //贡献的初始值为 x
        double x_contrubite = x;
        //在对N进行二进制拆分的同事计算方案
        while (N> 0) {
            if (N % 2== 1) {
                //如果N二进制表示的最低位置为1，那么需要计入贡献
                ans *= x_contrubite;
            }
            //将不断贡献平方
            x_contrubite *= x_contrubite;
            // 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
            N /= 2;
        }
        return ans;
    }

}
